package com.zj.leetcode.medium.greed;

/**
 * @program: algorithm
 * @description: 加油站
 * 134 gas-station
 * @author: Zhang Bo
 * @create: 2022-04-07 17:08:30
 **/
public class GasStation {
    public static void main(String[] args) {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        Solution solution = new GasStation().new Solution();
        System.out.println(solution.canCompleteCircuit(gas, cost));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {

            int sum = 0;
            int min = gas[0] - cost[0];
            int num = 0;
            for (int i = 0; i < gas.length; i++) {
                int temp = gas[i] - cost[i];
                if (min > sum + temp) {
                    min = sum + temp;
                    num = i;
                }
                sum = sum + temp;
            }

//            for (int i = 0; i < road.length; i++) {
//                if (min > sum + road[i]) {
//                    min = sum + road[i];
//                    num = i;
//                }
//                sum = sum + road[i];
//            }
            num = num == gas.length - 1 ? 0 : num + 1;
            return sum >= 0 ? num : -1;
        }

        public int canCompleteCircuit01(int[] gas, int[] cost) {
            int n = gas.length;
            int i = 0;
            while (i < n) {
                int sumOfGas = 0, sumOfCost = 0;
                int cnt = 0;
                while (cnt < n) {
                    int j = (i + cnt) % n;
                    sumOfGas += gas[j];
                    sumOfCost += cost[j];
                    if (sumOfCost > sumOfGas) {
                        break;
                    }
                    cnt++;
                }
                if (cnt == n) {
                    return i;
                } else {
                    i = i + cnt + 1;
                }
            }
            return -1;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}